// https://www.lintcode.com/problem/accounts-merge/description


class Solution {
public:
    /**
     * @param accounts: List[List[str]]
     * @return: return a List[List[str]]
     */
    map<string, string> father;
    map<string, string> name;
    void connect(string a, string b) {
        string fa = find(a);
        string fb = find(b);
        if (fa != fb)
        {
            father[fa] = fb;
        }
    }
    string find(string a) {
        string x = a;
        while (father[a] != a)
        {
            a = father[a];
        }
        while (x != a)
        {
            string tmp = father[x];
            father[x] = a;
            x = tmp;
        }
        return a;
    }
    vector<vector<string>> accountsMerge(vector<vector<string>> &accounts) {
        int n = accounts.size();
        vector<vector<string>> res;
        for (auto ac: accounts)
        {
            for (int i = 1; i < ac.size(); ++i)
            {
                if (father.find(ac[i]) == father.end()) 
                {
                    father[ac[i]] = ac[i];
                    name[ac[i]] = ac[0];
                }
                if (i != 1) connect(ac[i], ac[1]);
            }
        }
        map<string, vector<string>> mapRes;
        // for (auto f: father)
        // {
        //     mapRes[f.second].push_back(f.first); 并没有把所有的都直接连到根节点
        // }
        for (auto f: father)
        {
            mapRes[find(f.first)].push_back(f.first);
        }
        for (auto t: mapRes)
        {
            vector<string> tmpRes;
            tmpRes.push_back(name[t.first]);
            vector<string> emails = t.second;
            sort(emails.begin(), emails.end());
            tmpRes.insert(tmpRes.end(), emails.begin(), emails.end());
            res.push_back(tmpRes);
        }
        return res;
    }
};